#include "utility.h"
#include "memory.h"
#include "vector.h"

KL_BEGIN
template<typename Type, typename Allocate = KL::allocator<Type>>
class bstring
{
protected:	
	typedef KL::vector<Type, Allocate> _container;
	typedef KL::_memory_helper_<Type> _helper;
public:
	KL_TYPE_DEFINE(Type);
	STD_ITERATOR_DEFINE(typename _container::iterator);
	typedef typename Allocate::template rebind<value_type>::other allocator_type;
	static const size_type npos = -1;
protected:
	_container _c;
//	static const Type _null = 0;
	void _eos()
	{
		_c.push_back(0);
	}
	void _noeos()
	{
		_c.pop_back();
	}
	void _append(const_pointer cstr, size_t size)
	{
		_c.insert(_c.end(), cstr, cstr + size);
	}
	void _append(size_type num, value_type value)
	{
		_c.insert(_c.end(), num, value);
	}
	template<typename InIter>
	void _append(InIter first, InIter last)
	{
		_c.insert(_c.end(), first, last);
	}
	size_t _len(const_pointer cstr)
	{
		return ::strlen(cstr);
	}
public:
	bstring()
	{
		_eos();
	}
	bstring(const_pointer cstr)
	{
		_append(cstr, _len(cstr));
		_eos();
	}
	bstring(bstring const &o)
	{
		_append(o.data(), o.size());
		_eos();
	}
	bstring(const_pointer cstr, size_type num)
	{
		_append(cstr, num);
		_eos();
	}
	bstring(bstring const &o, size_type index, size_type num = npos)
	{
		ASSERT_REPAIR(index <= o.size(), index = o.size());
		if(index + num > o.size()) num = o.size() - index;
		_append(o.data() + index, num);
		_eos();
	}
	bstring(size_type num, value_type value)
	{
		_append(num, value);
		_eos();
	}
	template<typename InIter>
	bstring(InIter first, InIter last)
	{
		_append(first, last);
		_eos();
	}
	~bstring()
	{
	}
	bstring &append(const_pointer cstr)
	{
		this->append(cstr, strlen(cstr));
		return *this;
	}
	bstring &append(const_pointer cstr, size_type num)
	{
		if(cstr >= data() && cstr < data() + _c.capacity())
		{
			this->append(*this, cstr - data(), num);
		}
		else
		{
			_noeos();
			_append(cstr, num);
			_eos();
		}
		return *this;
	}
	bstring &append(bstring const &str)
	{
		if(this == &str)
		{
			_c.reserve(_c.size() * 2);
			_noeos();
			_append(_c.begin(), _c.size());
			_eos();
		}
		else
		{
			_noeos();
			_append(str.data(), str.size());
			_eos();
		}
		return *this;
	}
	bstring &append(bstring const &str, size_type index, size_type len)
	{
		ASSERT_REPAIR(index <= str.size(), return *this);
		if(index + len > str.size()) len = str.size() - index;
		if(this == &str)
		{
			_c.reserve(_c.size() + len);
			_noeos();
			_append(_c.begin() + index, _c.begin() + (index + len));
			_eos();
		}
		else
		{
			_noeos();
			_append(str.data() + index, len);
			_eos();
		}
		return *this;
	}
	bstring &append(size_type num, value_type value)
	{
		_noeos();
		_append(num, value);
		_eos();
		return *this;
	}
	template<typename InIter>
	bstring &append(InIter first, InIter last)
	{
		_noeos();
		_append(first, last);
		_eos();
		return *this;
	}
	// 
	bstring &assign(const_pointer cstr)
	{
		this->assign(cstr, strlen(cstr));
		return *this;
	}
	bstring &assign(const_pointer cstr, size_type num)
	{
		if(cstr >= data() && cstr < data() + _c.capacity())
		{
			this->assign(*this, cstr - data(), num);
		}
		else
		{
			_c.clear();
			_append(cstr, num);
			_eos();
		}
		return *this;
	}
	bstring &assign(bstring const &str)
	{
		if(this == &str) return *this;
		_c.clear();
		_append(str.data(), str.size());
		_eos();
		return *this;
	}
	bstring &assign(bstring const &str, size_type index, size_type len)
	{
		ASSERT_REPAIR(index <= str.size(), index = str.size());
		if(index + len > str.size()) len = str.size() - index;
		if(this == &str)
		{
			_noeos();
			_c.erase(_c.begin() + (index + len), _c.end());
			_c.erase(_c.begin(), _c.begin() + index);
			_eos();
		}
		else
		{
			_c.clear();
			_append(str.data() + index, len);
			_eos();
		}
		return *this;
	}
	bstring &assign(size_type num, value_type value)
	{
		_c.clear();
		_append(num, value);
		_eos();
		return *this;
	}
	template<typename InIter>
	bstring &assign(InIter first, InIter last)
	{
		_c.clear();
		_append(first, last);
		_eos();
		return *this;
	}
	bstring substr(size_type index, size_type num = npos)
	{
		ASSERT_REPAIR(index <= size(), index = size());
		if(index + num > size()) num = size() - index;
		return bstring(data(), num);
	}
	bstring &insert(size_type index, const_pointer cstr)
	{
		return this->insert(index, cstr, _len(cstr));
	}
	bstring &insert(size_type index, const_pointer cstr, size_type num)
	{
		if(cstr >= data() && cstr < data() + _c.capacity())
		{
			this->insert(index, *this, cstr - data(), num);
		}
		else
		{
			_noeos();
			_c.insert(_c.begin() + index, cstr, cstr + num);
			_eos();
		}
		return *this;
	}
	bstring &insert(size_type index, bstring const &str)
	{
		if(this == &str)
		{
			ASSERT_REPAIR(index <= size(), index = size());
			_noeos();
			size_type num = _c.size();
			_c.insert(_c.begin() + index, num);
			_helper::copy_n(_c.begin() + (index + num), num - index,
				_helper::copy_n(_c.begin(), index, _c.begin() + index));
			_eos();
		}
		else
		{
			_noeos();
			_c.insert(_c.begin() + index, str.begin(), str.end());
			_eos();
		}
		return *this;
	}
	bstring &insert(size_type index, bstring const &str, size_type i2, 
		size_type num)
	{
		ASSERT_REPAIR(i2 <= str.size(), i2 = str.size());
		if(i2 + num > str.size()) num = str.size() - i2;
		if(this == &str)
		{
			ASSERT_REPAIR(index <= size(), index = size());
			_noeos();
			_c.insert(_c.begin() + index, num);
			if(i2 >= index)
				_helper::copy_n(_c.begin() + (i2 + num), num, _c.begin() + index);
			else if(i2 + num <= index)
				_helper::copy_n(_c.begin(), num, _c.begin() + index);
			else
				_helper::copy_n(_c.begin() + (index + num), num - (index - i2),
					_helper::copy_n(_c.begin() + i2, index - i2, _c.begin() + index));
			_eos();
		}
		else
		{
			_noeos();
			_c.insert(_c.begin() + index, str.data() + i2, str.data() + (i2 + num));
			_eos();
		}
		return *this;
	}
	bstring &insert(size_type index, size_type num, value_type value)
	{
		_noeos();
		_c.insert(_c.begin() + index, num, value);
		_eos();
		return *this;
	}
	iterator insert(const_iterator pos, value_type value)
	{
		ASSERT_REPAIR(pos <= end(), pos = end());
		return _c.insert(pos, value);
	}
	iterator insert(const_iterator pos, size_type num, value_type value)
	{
		ASSERT_REPAIR(pos <= end(), pos = end());
		return _c.insert(pos, num, value);
	}
	template<typename InIter>
	iterator insert(const_iterator pos, InIter first, InIter last)
	{
		ASSERT_REPAIR(pos <= end(), pos = end());
		return _c.insert(pos, first, last);
	}
	bstring &erase(size_type index = 0, size_type num = npos)
	{
		ASSERT_REPAIR(index <= size(), index = size());
		if(index + num > size()) num = size() - index;
		_noeos();
		_c.erase(_c.begin() + index, num);
		_eos();
		return *this;
	}
	iterator erase(const_iterator loc)
	{
		ASSERT_REPAIR(loc < end(), return end());
		return _c.erase(loc);
	}
	iterator erase(const_iterator first, const_iterator last)
	{
		ASSERT_REPAIR(last <= end(), last = end());
		return _c.erase(first, last);
	}
	void resize(size_type num, value_type value = value_type())
	{
		_noeos();
		_c.resize(num, value);
		_eos();
	}
	void swap(bstring const &o)
	{
		_c.swap(o._c);
	}
	void clear()
	{
		_c.clear();
		_eos();
	}
	void push_back(Type const &value)
	{
		_noeos();
		_c.push_back(value);
		_eos();
	}
	void pop_back()
	{
		_noeos();
		_c.pop_back();
		_eos();
	}
	void reserve(size_type num)
	{
		_c.reserve(num + 1);
	}
	// ....
	size_t length() const
	{
		return size();
	}
	size_t size() const
	{
		return _c.size() - 1;
	}
	size_t capacity() const
	{
		return _c.capacity() - 1;
	}
	size_t max_size() const
	{
		return _c.max_size() - 1;
	}
	bool empty() const
	{
		return _c.size() <= 1;
	}
	value_type & at(size_type pos)
	{
		return _c.at(pos);
	}
	value_type const & at(size_type pos) const
	{
		return _c.at(pos);
	}
	value_type & operator [] (size_type pos)
	{
		return _c[pos];
	}
	value_type const & operator [](size_type pos) const
	{
		return _c[pos];
	}
	const_pointer c_str() const
	{
		return data();
	}
	const_pointer data() const
	{
		return _c.begin();
	}
	iterator begin()
	{
		return _c.begin();
	}
	iterator end()
	{
		return _c.end() - 1;
	}
	const_iterator begin() const
	{
		return _c.begin();
	}
	const_iterator end() const
	{
		return _c.end() - 1;
	}
	reverse_iterator rbegin()
	{
		return _c.rbegin() + 1;
	}
	reverse_iterator rend()
	{
		return _c.rend();
	}
	const_reverse_iterator rbegin() const
	{
		return _c.rbegin() + 1;
	}
	const_reverse_iterator rend() const
	{
		return _c.rend();
	}
public: // compare
	bool operator == (bstring const &o) const
	{
		return ::strcmp(data(), o.data()) == 0;
	}
	bool operator < (bstring const &o) const
	{
		return ::strcmp(data(), o.data()) < 0;
	}
	bool operator > (bstring const &o) const
	{
		return o < *this;
	}
	bool operator != (bstring const &o) const
	{
		return !(*this == o);
	}
	bool operator <= (bstring const &o) const
	{
		return !(o < *this);
	}
	bool operator >= (bstring const &o) const
	{
		return !(*this < o);
	}
};
typedef bstring<char> string;
KL_END
